Edge Cut

Definition / 定义

edge cut（边割/割边集合）：在图论中，指一组边，把这些边从图中移除后，会使图变得不连通，或把顶点集合分成两个（或多个）部分；常用于图划分、网络可靠性与并行计算等语境。（在某些语境下也可泛指“沿边缘的切割”，但更常见的是图论义项。）

Pronunciation / 发音（IPA）

/ˈedʒ kʌt/

Examples / 例句

Removing a single bridge edge creates an edge cut.
移除一条桥边就形成了一个边割。

In graph partitioning, we try to minimize the edge cut between two groups of nodes to reduce communication cost.
在图划分中，我们会尽量最小化两组节点之间的边割，以降低通信成本。

Etymology / 词源

edge 源自古英语 ecg，本义为“边缘、刃”；cut 源自古英语 cyttan，意为“切割”。组合成 edge cut，直观表达“切断（某些）边”，在图论里进一步专指“切掉一组边使图分离”的概念。

Related Words / 相关词汇

• Cut
• Edge
• Vertex Cut
• Cut Set
• Cut Edge
• Bridge
• Graph Partitioning
• Min-Cut
• Max-Flow

Literary Works / 文献与作品中的用例

• Introduction to Graph Theory（Douglas B. West）——在割（cut）、连通性（connectivity）相关章节中讨论边割等概念。
• Graph Theory（Reinhard Diestel）——在图的连通性与割集的语境中使用与“edge cut”对应的术语与定义。
• Computational Geometry: Algorithms and Applications（de Berg 等）——在图划分/网格与相关算法讨论中涉及“cut/partition”类概念与术语。